package leetcode;

import common.ListNode;
import common.Util;

/**
 * K 个一组翻转链表
 */
public class LeetCode25 {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || head.next == null) return head;
        int length = getLength(head);
        int n = length / k;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prevTail = dummy;
        for (int i = 0; i < n; i++) {
            ListNode newHead = reverse(head, k);
            prevTail.next = newHead;
            prevTail = head;
            head = head.next;
        }
        return dummy.next;
    }

    private ListNode reverse(ListNode head, int k) {
        ListNode prev = null, cur = head;
        for (int i = 0; i < k; i++) {
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        head.next = cur;
        return prev;
    }

    private int getLength(ListNode head) {
        int length = 0;
        while (head != null) {
            head = head.next;
            length++;
        }
        return length;
    }

    public static void main(String[] args) {
        LeetCode25 leetCode25 = new LeetCode25();
        Util.formatListNode(leetCode25.reverseKGroup(Util.createListNode(5), 2));
    }
}